#include "string_array.h"
#include <cstring>

using namespace std;

// myStr构造函数
myStr::myStr(const char* str) {
    if (str == nullptr) {
        length = 0;
        data = new char[1];
        data[0] = '\0';
    } else {
        length = strlen(str);
        data = new char[length + 1];
        strcpy(data, str);
    }
    next = nullptr;
    nextVal = nullptr;
}

// myStr析构函数
myStr::~myStr() {
    delete[] data;
    delete[] next;
    delete[] nextVal;
}

void myStr::print(){
    for(int i = 0; i < this->length; i++)
        cout << this->data[i];

    cout << endl;
}

void myStr::printNext(){
    for(int i = 0; i < length; i++)
        cout << next[i];
    cout << endl;
}

void myStr::printNextVal(){
    for(int i = 0; i < length; i++)
        cout << nextVal[i];
    cout << endl;
}

// KMP next数组计算（按照教材中的1号下标写法实现，再映射到0号下标）
void myStr::kmp_next() {
    if (length == 0) return;

    // 临时数组采用1..length的下标，temp[0]不用
    int* temp = new int[length + 1];
    temp[1] = 0;

    int i = 1;      // 已经求得next值的位置
    int j = 0;      // 当前最长相等前后缀长度
    while (i < length) {
        if (j == 0 || data[i - 1] == data[j - 1]) {
            ++i;
            ++j;
            if (i <= length)
                temp[i] = j;
        } else {
            j = temp[j];
        }
    }

    // 将1..length的结果拷贝到0..length-1
    delete[] next;
    next = new int[length];
    for (int k = 1; k <= length; ++k) {
        next[k - 1] = temp[k];
    }

    delete[] temp;
}

// KMP nextVal数组计算（同样使用1号下标写法）
void myStr::kmp_nextVal() {
    if (length == 0) return;

    // 先得到普通next（内部会分配并填充成员 next[0..length-1]）
    kmp_next();

    // 把next拷贝到1..length的临时数组中，便于按教材公式计算nextVal
    int* tempNext = new int[length + 1];
    int* tempNextVal = new int[length + 1];
    tempNext[1] = 0;
    for (int i = 2; i <= length; ++i) {
        tempNext[i] = next[i - 1];
    }

    tempNextVal[1] = 0;
    for (int i = 2; i <= length; ++i) {
        if (tempNext[i] == 0 || data[i - 1] != data[tempNext[i] - 1]) {
            tempNextVal[i] = tempNext[i];
        } else {
            tempNextVal[i] = tempNextVal[tempNext[i]];
        }
    }

    // 写回到成员 nextVal[0..length-1]
    delete[] nextVal;
    nextVal = new int[length];
    nextVal[0] = 0;
    for (int i = 2; i <= length; ++i) {
        nextVal[i - 1] = tempNextVal[i];
    }

    delete[] tempNext;
    delete[] tempNextVal;
}

// 简单字符串匹配算法
int simpleMatch(const myStr& S, const myStr& T) {
    int sLen = S.length;
    int tLen = T.length;
    
    if (tLen == 0 || sLen < tLen) return -1;
    
    for (int i = 0; i <= sLen - tLen; i++) {
        int j = 0;
        while (j < tLen && S.data[i + j] == T.data[j]) {
            j++;
        }
        if (j == tLen) {
            return i + 1; // 位置从1开始
        }
    }
    
    return -1;
}

// KMP字符串匹配算法（使用改进的nextVal）
int kmpMatch(const myStr& S, const myStr& T) {
    int sLen = S.length;
    int tLen = T.length;

    if (tLen == 0 || sLen < tLen) return -1;

    // 为模式串T计算nextVal（内部会同时算出next）
    myStr pattern(T.data);
    pattern.kmp_nextVal();

    // 将 pattern.nextVal[0..tLen-1] 视为 1..tLen 的 nextVal
    int i = 1; // 目标串下标（1..sLen）
    int j = 1; // 模式串下标（1..tLen）

    while (i <= sLen && j <= tLen) {
        if (j == 0 || S.data[i - 1] == T.data[j - 1]) {
            ++i;
            ++j;
        } else {
            j = pattern.nextVal[j - 1];
        }
    }

    if (j > tLen) {
        return i - tLen; // 位置从1开始
    }

    return -1;
}

// 字符串替换函数
bool replaceStr(myStr& S, const int& start, const myStr& T, const myStr& V) {
    // start从1开始，转换为从0开始
    int startPos = start - 1;
    
    if (startPos < 0 || startPos >= S.length) return false;
    
    // 在S中从start位置开始向后搜索子串T
    int sLen = S.length;
    int tLen = T.length;
    int vLen = V.length;
    
    if (tLen == 0) return false;
    
    // 从startPos开始向后搜索T
    int foundPos = -1;
    for (int i = startPos; i <= sLen - tLen; i++) {
        bool match = true;
        for (int j = 0; j < tLen; j++) {
            if (S.data[i + j] != T.data[j]) {
                match = false;
                break;
            }
        }
        if (match) {
            foundPos = i;
            break;
        }
    }
    
    if (foundPos == -1) return false;
    
    // 执行替换
    int newLen = sLen - tLen + vLen;
    char* newData = new char[newLen + 1];
    
    // 复制foundPos之前的部分
    for (int i = 0; i < foundPos; i++) {
        newData[i] = S.data[i];
    }
    
    // 复制V
    for (int i = 0; i < vLen; i++) {
        newData[foundPos + i] = V.data[i];
    }
    
    // 复制foundPos + tLen之后的部分
    for (int i = foundPos + tLen; i < sLen; i++) {
        newData[foundPos + vLen + (i - foundPos - tLen)] = S.data[i];
    }
    
    newData[newLen] = '\0';
    
    delete[] S.data;
    S.data = newData;
    S.length = newLen;
    
    return true;
}

void myMatrix::printMatrix(){
    cout << rowNum << "," << colNum << "," << nodeNum << endl;

    for(int i = 0; i < nodeNum; i++)
        cout << nodeList[i].row << "," << nodeList[i].col << "," << nodeList[i].value << endl;
}

// myMatrix构造函数（带参数）
myMatrix::myMatrix(const int& rNum, const int& cNum, const int& nNum, const int* arr) {
    rowNum = rNum;
    colNum = cNum;
    nodeNum = nNum;
    
    if (nNum > 0 && arr != nullptr) {
        nodeList = new matrixNode[nNum];
        for (int i = 0; i < nNum; i++) {
            nodeList[i].row = arr[i * 3];
            nodeList[i].col = arr[i * 3 + 1];
            nodeList[i].value = arr[i * 3 + 2];
        }
    } else {
        nodeList = nullptr;
    }
}

// myMatrix默认构造函数
myMatrix::myMatrix() {
    rowNum = 0;
    colNum = 0;
    nodeNum = 0;
    nodeList = nullptr;
}

// myMatrix析构函数
myMatrix::~myMatrix() {
    delete[] nodeList;
    nodeList = nullptr;
}

// 快速转置算法
void myMatrix::FastTransposeSMatrix(myMatrix& T) {
    if (nodeNum == 0) {
        T.rowNum = colNum;
        T.colNum = rowNum;
        T.nodeNum = 0;
        T.nodeList = nullptr;
        return;
    }
    
    // 统计每列（转置后的行）的非零元素个数
    int* num = new int[colNum];
    int* cpot = new int[colNum];
    
    for (int i = 0; i < colNum; i++) {
        num[i] = 0;
    }
    
    for (int i = 0; i < nodeNum; i++) {
        num[nodeList[i].col]++;
    }
    
    // 计算每列（转置后的行）的第一个非零元素在转置矩阵中的位置
    cpot[0] = 0;
    for (int i = 1; i < colNum; i++) {
        cpot[i] = cpot[i - 1] + num[i - 1];
    }
    
    // 分配转置矩阵的空间
    T.rowNum = colNum;
    T.colNum = rowNum;
    T.nodeNum = nodeNum;
    delete[] T.nodeList;
    T.nodeList = new matrixNode[nodeNum];
    
    // 执行转置
    for (int i = 0; i < nodeNum; i++) {
        int col = nodeList[i].col;
        int pos = cpot[col];
        T.nodeList[pos].row = nodeList[i].col;
        T.nodeList[pos].col = nodeList[i].row;
        T.nodeList[pos].value = nodeList[i].value;
        cpot[col]++;
    }
    
    delete[] num;
    delete[] cpot;
}

